package com.yc.project3_bestMatching;

public class Editdistances {
    /**
     * 计算从word1变为word2要编辑几次=> 编辑距离。 计算两个字符串之间的编辑距离。
     * 编辑距离是指将一个字符串转换为另一个字符串所需的最少操作次数，操作包括插入、删除和替换字符。
     *
     * @param word1 第一个字符串
     * @param word2 第二个字符串
     * @return 两个字符串之间的编辑距离
     */
    public static int calculator(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        // 创建一个二维数组来存储子问题的解
        int[][] distances = new int[m + 1][n + 1];
        // 初始化第一列的值
        for (int i = 0; i <= m; i++) {
            distances[i][0] = i;
        }
        for (int j = 0; j <= n; j++) { //第一行
            distances[0][j] = j;
        }
        // 填充二维数组的其余部分
        for (int i =1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前字符相同，则不需要进行任何操作
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    distances[i][j] = distances[i - 1][j - 1];
                } else {
                    // 否则，取三种操作中的最小值并加一
                    distances[i][j]=minimum(distances[i-1][j], distances[i][j-1] , distances[i-1][j-1])+1;
                }
            }
        }
        // 返回最后一个单元格的值，即两个字符串的编辑距离
        return distances[m][n];
    }
    public static int minimum(int i, int j, int k) {
        return Math. min(i, Math.min(j, k));
    }
}
